package me.zk;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 快速排序，非递归实现
 * @Author: zhang kai
 * @Date: 2022/06/27
 * @Description:
 */
public class QuickSortDemo3 {


    public static void quickSort(int[] array, int startIndex, int endIndex) {
        Stack<Map<String,Integer>> quickSortStack = new Stack<>();

        Map rootParam = new HashMap();
        rootParam.put("startIndex",startIndex);
        rootParam.put("endIndex",endIndex);
        quickSortStack.push(rootParam);
        while(!quickSortStack.isEmpty()) {
            Map<String,Integer> param = quickSortStack.pop();
            //
            int pivotIndex = partition(array,param.get("startIndex"),param.get("endIndex"));
            if (param.get("startIndex") < pivotIndex -1) {
                Map<String,Integer> leftParam = new HashMap<>();
                leftParam.put("startIndex",param.get("startIndex"));
                leftParam.put("endIndex",pivotIndex-1);
                quickSortStack.push(leftParam);
            }
            if (pivotIndex+1 < param.get("endIndex")) {
                Map<String, Integer> rightParam = new HashMap<>();
                rightParam.put("startIndex",pivotIndex+1);
                rightParam.put("endIndex",param.get("endIndex"));
                quickSortStack.push(rightParam);
            }
        }
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        //取第一个位置（也可以选择随机位置）的元素作为基准元素
        int pivot = arr[startIndex];
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int p = arr[mark];
                arr[mark] = arr[i];
                arr[i] = p;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
        int[] array = {4,4,6,5,3,2,8,1,0,12};
        quickSort(array,0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}
